
class TreeNode {
    int val;
      TreeNode left;
      TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
         this.right = right;
      }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                '}';
    }
}


class Solution {
     int preIndex ;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder , inorder , 0 , inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder ,
                                    int[] inorder , int begin , int end){
        if(preIndex > preorder.length - 1 || begin > end){
            return null ;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findIndex(inorder , begin , end , preorder[preIndex]);
        if(rootIndex == -1){
            return null ;
        }
        preIndex ++ ;
        root.left = buildTreeChild(preorder ,  inorder ,
                begin , rootIndex - 1 );
        root.right = buildTreeChild(preorder ,  inorder ,
                rootIndex + 1 , end) ;
        return root ;
    }
    private int findIndex( int[] inorder , int begin , int end , int key){
        for(int i = begin ; i<= end ; i ++){
            if (inorder[i] == key){
                return i ;
            }
        }
        return -1 ;
    }

}